Maximize the sum ratio
Let S be K positive sequences Ai, Bi of length N. We want to maximize the Ratio of the sum of each of AB $ \argmax_S { \sum_{i\in S} B_i \over \sum_{i\in S} A_i }
Instead of directly maximizing the ratio of sums, there is a solution method that makes it a problem of determining whether the ratio of sums is greater than or equal to X, and then bisectively searching for X
$ {\sum B_i \over \sum A_i} \ge X
$ \sum B_i \ge X \sum A_i
$ \sum B_i - X \sum A_i \ge 0
$ \sum (B_i - X A_i) \ge 0
If there exists an S satisfying the condition, then the K selections from which $ B_i - X A_i is larger satisfy the condition.
Therefore, this decision problem can be solved by O(NlogN).
A dichotomous search of this X will find the largest X for which S satisfies the condition. This is the maximum value of X. ---
This page is auto-translated from /nishio/和の比率の最大化. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.